Decode ways II

Time: O(N); Space: O(1); hard

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

  • ‘A’ -> 1

  • ‘B’ -> 2

  • …

  • ‘Z’ -> 26

Beyond that, now the encoded string can also contain the character ’*’, which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character ’*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

Input: s = “*”

Output: 9

Explanation:

  • The encoded message can be decoded to the string: “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H”, “I”.

Example 2:

Input: s = “1*”

Output: 18

Explanation:

  • 9 + 9 = 18

Constraints:

  • The length of the input string will fit in range [1, 105].

  • The input string will only contain the character ’*’ and digits ‘0’ - ‘9’.

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        M, W = 1000000007, 3
        dp = [0] * W
        dp[0] = 1
        dp[1] = 9 if s[0] == '*' else dp[0] if s[0] != '0' else 0

        for i in range(1, len(s)):
            if s[i] == '*':
                dp[(i + 1) % W] = 9 * dp[i % W]
                if s[i - 1] == '1':
                    dp[(i + 1) % W] = (dp[(i + 1) % W] + 9 * dp[(i - 1) % W]) % M
                elif s[i - 1] == '2':
                    dp[(i + 1) % W] = (dp[(i + 1) % W] + 6 * dp[(i - 1) % W]) % M
                elif s[i - 1] == '*':
                    dp[(i + 1) % W] = (dp[(i + 1) % W] + 15 * dp[(i - 1) % W]) % M
            else:
                dp[(i + 1) % W] = dp[i % W] if s[i] != '0' else 0
                if s[i - 1] == '1':
                    dp[(i + 1) % W] = (dp[(i + 1) % W] + dp[(i - 1) % W]) % M
                elif s[i - 1] == '2' and s[i] <= '6':
                    dp[(i + 1) % W] = (dp[(i + 1) % W] + dp[(i - 1) % W]) % M
                elif s[i - 1] == '*':
                    dp[(i + 1) % W] = (dp[(i + 1) % W] + (2 if s[i] <= '6' else 1) * dp[(i - 1) % W]) % M

        return dp[len(s) % W]

[4]:

sol = Solution1()

s = "*"
assert sol.numDecodings(s) == 9

s = "1*"
assert sol.numDecodings(s) == 18